๐Ÿ‘ฉโ€๐Ÿ’ป 17779. ๊ฒŒ๋ฆฌ๋งจ๋”๋ง 2

@Seongukbaek Posted March 20, 2022 ยท Updated March 20, 2022 ยท 8 min read

๋ฌธ์ œ

์žฌํ˜„์‹œ์˜ ์‹œ์žฅ ๊ตฌ์žฌํ˜„์€ ์ง€๋‚œ ๋ช‡ ๋…„๊ฐ„ ๊ฒŒ๋ฆฌ๋งจ๋”๋ง์„ ํ†ตํ•ด์„œ ์ž์‹ ์˜ ๋‹น์—๊ฒŒ ์œ ๋ฆฌํ•˜๊ฒŒ ์„ ๊ฑฐ๊ตฌ๋ฅผ ํš์ •ํ–ˆ๋‹ค. ๊ฒฌ์ œํ•  ๊ถŒ๋ ฅ์ด ์—†์–ด์ง„ ๊ตฌ์žฌํ˜„์€ ๊ถŒ๋ ฅ์„ ๋งค์šฐ ๋ถ€๋‹นํ•˜๊ฒŒ ํ–‰์‚ฌํ–ˆ๊ณ , ์‹ฌ์ง€์–ด๋Š” ์‹œ์˜ ์ด๋ฆ„๋„ ์žฌํ˜„์‹œ๋กœ ๋ณ€๊ฒฝํ–ˆ๋‹ค. ์ด๋ฒˆ ์„ ๊ฑฐ์—์„œ๋Š” ์ตœ๋Œ€ํ•œ ๊ณตํ‰ํ•˜๊ฒŒ ์„ ๊ฑฐ๊ตฌ๋ฅผ ํš์ •ํ•˜๋ ค๊ณ  ํ•œ๋‹ค.

์žฌํ˜„์‹œ๋Š” ํฌ๊ธฐ๊ฐ€ Nร—N์ธ ๊ฒฉ์ž๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๊ฒฉ์ž์˜ ๊ฐ ์นธ์€ ๊ตฌ์—ญ์„ ์˜๋ฏธํ•˜๊ณ , rํ–‰ c์—ด์— ์žˆ๋Š” ๊ตฌ์—ญ์€ (r, c)๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๊ตฌ์—ญ์„ ๋‹ค์„ฏ ๊ฐœ์˜ ์„ ๊ฑฐ๊ตฌ๋กœ ๋‚˜๋ˆ ์•ผ ํ•˜๊ณ , ๊ฐ ๊ตฌ์—ญ์€ ๋‹ค์„ฏ ์„ ๊ฑฐ๊ตฌ ์ค‘ ํ•˜๋‚˜์— ํฌํ•จ๋˜์–ด์•ผ ํ•œ๋‹ค. ์„ ๊ฑฐ๊ตฌ๋Š” ๊ตฌ์—ญ์„ ์ ์–ด๋„ ํ•˜๋‚˜ ํฌํ•จํ•ด์•ผ ํ•˜๊ณ , ํ•œ ์„ ๊ฑฐ๊ตฌ์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ๊ตฌ์—ญ์€ ๋ชจ๋‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์–ด์•ผ ํ•œ๋‹ค. ๊ตฌ์—ญ A์—์„œ ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์„ ํ†ตํ•ด์„œ ๊ตฌ์—ญ B๋กœ ๊ฐˆ ์ˆ˜ ์žˆ์„ ๋•Œ, ๋‘ ๊ตฌ์—ญ์€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๊ณ  ํ•œ๋‹ค. ์ค‘๊ฐ„์— ํ†ตํ•˜๋Š” ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์€ 0๊ฐœ ์ด์ƒ์ด์–ด์•ผ ํ•˜๊ณ , ๋ชจ๋‘ ๊ฐ™์€ ์„ ๊ฑฐ๊ตฌ์— ํฌํ•จ๋œ ๊ตฌ์—ญ์ด์–ด์•ผ ํ•œ๋‹ค.

์„ ๊ฑฐ๊ตฌ๋ฅผ ๋‚˜๋ˆ„๋Š” ๋ฐฉ๋ฒ•์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  1. ๊ธฐ์ค€์  (x, y)์™€ ๊ฒฝ๊ณ„์˜ ๊ธธ์ด d1, d2๋ฅผ ์ •ํ•œ๋‹ค. (d1, d2 โ‰ฅ 1, 1 โ‰ค x < x+d1+d2 โ‰ค N, 1 โ‰ค y-d1 < y < y+d2 โ‰ค N)
  2. ๋‹ค์Œ ์นธ์€ ๊ฒฝ๊ณ„์„ ์ด๋‹ค.

    1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
    2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
    3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
    4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
  3. ๊ฒฝ๊ณ„์„ ๊ณผ ๊ฒฝ๊ณ„์„ ์˜ ์•ˆ์— ํฌํ•จ๋˜์–ด์žˆ๋Š” ๊ณณ์€ 5๋ฒˆ ์„ ๊ฑฐ๊ตฌ์ด๋‹ค.
  4. 5๋ฒˆ ์„ ๊ฑฐ๊ตฌ์— ํฌํ•จ๋˜์ง€ ์•Š์€ ๊ตฌ์—ญ (r, c)์˜ ์„ ๊ฑฐ๊ตฌ ๋ฒˆํ˜ธ๋Š” ๋‹ค์Œ ๊ธฐ์ค€์„ ๋”ฐ๋ฅธ๋‹ค.

    1. 1๋ฒˆ ์„ ๊ฑฐ๊ตฌ: 1 โ‰ค r < x+d1, 1 โ‰ค c โ‰ค y
    2. 2๋ฒˆ ์„ ๊ฑฐ๊ตฌ: 1 โ‰ค r โ‰ค x+d2, y < c โ‰ค N
    3. 3๋ฒˆ ์„ ๊ฑฐ๊ตฌ: x+d1 โ‰ค r โ‰ค N, 1 โ‰ค c < y-d1+d2
    4. 4๋ฒˆ ์„ ๊ฑฐ๊ตฌ: x+d2 < r โ‰ค N, y-d1+d2 โ‰ค c โ‰ค N

์•„๋ž˜๋Š” ํฌ๊ธฐ๊ฐ€ 7ร—7์ธ ์žฌํ˜„์‹œ๋ฅผ ๋‹ค์„ฏ ๊ฐœ์˜ ์„ ๊ฑฐ๊ตฌ๋กœ ๋‚˜๋ˆˆ ๋ฐฉ๋ฒ•์˜ ์˜ˆ์‹œ์ด๋‹ค.

๊ตฌ์—ญ (r, c)์˜ ์ธ๊ตฌ๋Š” A[r][c]์ด๊ณ , ์„ ๊ฑฐ๊ตฌ์˜ ์ธ๊ตฌ๋Š” ์„ ๊ฑฐ๊ตฌ์— ํฌํ•จ๋œ ๊ตฌ์—ญ์˜ ์ธ๊ตฌ๋ฅผ ๋ชจ๋‘ ํ•ฉํ•œ ๊ฐ’์ด๋‹ค. ์„ ๊ฑฐ๊ตฌ๋ฅผ ๋‚˜๋ˆ„๋Š” ๋ฐฉ๋ฒ• ์ค‘์—์„œ, ์ธ๊ตฌ๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ์„ ๊ฑฐ๊ตฌ์™€ ๊ฐ€์žฅ ์ ์€ ์„ ๊ฑฐ๊ตฌ์˜ ์ธ๊ตฌ ์ฐจ์ด์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•ด๋ณด์ž.

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— ์žฌํ˜„์‹œ์˜ ํฌ๊ธฐ N์ด ์ฃผ์–ด์ง„๋‹ค.
  • ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— N๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. rํ–‰ c์—ด์˜ ์ •์ˆ˜๋Š” A[r][c]๋ฅผ ์˜๋ฏธํ•œ๋‹ค.

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— ์ธ๊ตฌ๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ์„ ๊ฑฐ๊ตฌ์™€ ๊ฐ€์žฅ ์ ์€ ์„ ๊ฑฐ๊ตฌ์˜ ์ธ๊ตฌ ์ฐจ์ด์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Dosi { int N; int minDiff = Integer.MAX_VALUE; int[][] map; int[][] copyMap; int[] rangeX = { -1, 0, 1, 0 }; int[] rangeY = { 0, 1, 0, -1 }; ... }
  • ์„ ๊ฑฐ๊ตฌ์˜ ์ •๋ณด๋ฅผ ๋‹ด๋‹นํ•˜๋Š” ํด๋ž˜์Šค์ด๋‹ค.
public int vote() {...}
  • ์ฃผ์–ด์ง„ ๊ธฐ์ค€์— ๋”ฐ๋ผ ์„ ๊ฑฐ๊ตฌ๋ฅผ ๋‚˜๋ˆ„๊ณ , ์ธ๊ตฌ ์ˆ˜๋ฅผ ํ•ฉ์‚ฐํ•˜๋Š” ๋กœ์ง์„ ์‹คํ–‰ํ•˜๋Š” ๋ฉ”์†Œ๋“œ์ด๋‹ค.
private void setLine(int x, int y, int d1, int d2) {...}
  • 5๋ฒˆ ์„ ๊ฑฐ๊ตฌ์˜ ๊ฐ€์žฅ์ž๋ฆฌ๋ฅผ ๊ธ‹๊ณ , ๋‚ด๋ถ€ ์˜์—ญ์„ ํƒ์ƒ‰ํ•˜๋Š” isConnected ๋ฅผ ์‹คํ–‰ํ•˜๋Š” ๋ฉ”์†Œ๋“œ์ด๋‹ค.
private void isConnected(int x, int y) {...}
  • ์žฌ๊ท€์ ์œผ๋กœ 5๋ฒˆ ์„ ๊ฑฐ๊ตฌ์˜ ๋‚ด๋ถ€๋ฅผ ํƒ์ƒ‰ํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Dosi { int N; int minDiff = Integer.MAX_VALUE; int[][] map; int[][] copyMap; int[] rangeX = { -1, 0, 1, 0 }; int[] rangeY = { 0, 1, 0, -1 }; public Dosi(int N) { this.N = N; map = new int[N + 1][N + 1]; } public int vote() { for (int d1 = 1; d1 <= N; d1++) { for (int d2 = 1; d2 <= N; d2++) { for (int x = 1; x <= N; x++) { for (int y = 1; y <= N; y++) { if (!(x + d1 + d2 <= N && y - d1 >= 1 && y + d2 <= N)) continue; copyMap = new int[N + 1][N + 1]; popSum1(x, y, d1); popSum2(x, y ,d2); popSum3(x, y, d1, d2); popSum4(x, y, d1, d2); setLine(x, y, d1, d2); sum(); } } } } return minDiff; } private void sum() { int max = 0; int min = Integer.MAX_VALUE; int[] popSum = new int[6]; for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { popSum[copyMap[i][j]]+=map[i][j]; } } for(int i=1; i<=5; i++) { max = Math.max(max, popSum[i]); min = Math.min(min, popSum[i]); } minDiff = Math.min(minDiff, max-min); } private void setLine(int x, int y, int d1, int d2) { for(int i = 0; i <= d1; i++) { copyMap[x+i][y-i] = 5; } for(int i = 0; i <= d2; i++) { copyMap[x+i][y+i] = 5; } for(int i = 0; i <= d2; i++) { copyMap[x+d1+i][y-d1+i] = 5; } for(int i = 0; i <= d1; i++) { copyMap[x+d2+i][y+d2-i] = 5; } for(int alpha = 0; alpha < d1; alpha++) { isConnected(x+alpha+1, y-alpha); } for(int alpha = 0; alpha < d2; alpha++) { isConnected(x+alpha+1, y+alpha); } } private void isConnected(int x, int y) { copyMap[x][y] = 5; for(int i=0; i<4; i++) { int nx = x + rangeX[i]; int ny = y + rangeY[i]; if (nx < 1 || nx > N || ny < 1 || ny > N) continue; if (copyMap[nx][ny] != 5) isConnected(nx,ny); } } private void popSum1(int x, int y, int d1) { for (int i = 1; i < x + d1; i++) { for (int j = 1; j <= y; j++) { copyMap[i][j] = 1; } } } private void popSum2(int x, int y, int d2) { for (int i = 1; i <= x + d2; i++) { for (int j = y + 1; j <= N; j++) { copyMap[i][j] = 2; } } } private void popSum3(int x, int y, int d1, int d2) { for (int i = x + d1; i <= N; i++) { for (int j = 1; j < y - d1 + d2; j++) { copyMap[i][j] = 3; } } } private void popSum4(int x, int y, int d1, int d2) { for (int i = x + d2 + 1; i <= N; i++) { for (int j = y - d1 + d2; j <= N; j++) { copyMap[i][j] = 4; } } } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Dosi dosi = new Dosi(N); String[] line; for (int i = 1; i <= N; i++) { line = br.readLine().split(" "); for (int j = 1; j <= N; j++) { dosi.map[i][j] = Integer.parseInt(line[j - 1]); } } System.out.println(dosi.vote()); br.close(); } }

โœ๏ธ Review

  • ์ฒ˜์Œ์—๋Š” ๊ฒŒ๋ฆฌ๋งจ๋”๋ง์ด๋ž‘ ๋น„์Šทํ•œ ์ค„ ์•Œ์•˜๋Š”๋ฐ ์กฐ๊ธˆ์€ ๋‹ฌ๋ผ์„œ ์ƒ๊ฐํ•ด๋ณด๋Š”๋ฐ ์‹œ๊ฐ„์ด ์ข€ ๊ฑธ๋ ธ๋‹ค.
  • ์„ ๊ฑฐ๊ตฌ๋ฅผ ๋‚˜๋ˆ„๋Š” ๋กœ์ง์„ ๊ตฌํ˜„ํ•˜๋Š”๋ฐ ์‹œ๊ฐ„์ด ๊ฑธ๋ ธ๊ณ , ๊ฒŒ์‹œํŒ์„ ์ฐธ๊ณ ํ•ด์„œ ๋‚˜๋ฆ„๋Œ€๋กœ ํ’€์–ด๋ดค๋Š”๋ฐ, ์ตœ์ข…์ ์œผ๋กœ ์ธ๊ตฌ์ˆ˜๋ฅผ ํ•ฉ์‚ฐํ•ด ์ฐจ์ด์˜ ์ตœ์†Œ๋ฅผ ๊ตฌํ•˜๋Š” ๋กœ์ง์ด ์ž๊พธ ํ‹€๋ ธ๋‹ค.

    • ์–ด์ฐจํ”ผ ๋‚˜๋ˆ ์ง„ ์„ ๊ฑฐ๊ตฌ์˜ ์ธ๊ตฌ ์ˆ˜๋ฅผ ๋‚˜๋ˆŒ ๋•Œ๋งˆ๋‹ค ํ•ฉ์‚ฐํ•˜๊ณ  ์„ ๊ฑฐ๊ตฌ๋ฅผ ๋‹ค ๋‚˜๋ˆˆ ๋’ค (์ฆ‰, ์ธ๊ตฌ ์ˆ˜ ํ•ฉ์‚ฐ๊นŒ์ง€ ์™„๋ฃŒ๋œ ์ƒํƒœ) ์ฐจ์ด๋ฅผ ๊ตฌํ•˜๊ณ  ์ด๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๋Š” ๋ฐฉ์‹์€ ์™œ ํ‹€๋ฆฌ๋Š”์ง€ ๋ชจ๋ฅด๊ฒ ๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

Baekjoon : https://www.acmicpc.net/problem/17779

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€